1. Field of the Invention
This invention relates generally to data caching, and more particularly to a system and method for caching texture map information in a graphics rendering system.
2. Description of the Background Art
Systems that implement interactive three-dimensional graphics rendering commonly operate by transforming, shading, clipping and projecting three-dimensional geometric data to generate triangles with vertices in two-dimensional coordinates. Typically, these screen space triangles are rasterized by a method called "smooth shading."
FIG. 1 through FIG. 5D illustrate briefly conventional smooth-shading techniques for generating a texture (color) map from picture information. FIG. 1 shows a triangular object T having three vertices, a first at (X.sub.0,Y.sub.0) with a texture value equal to (U.sub.0,V.sub.0), a second at (X.sub.1,Y.sub.1) with a texture value equal to. (U.sub.1,V.sub.1), and a third at (X.sub.2,Y.sub.0) with a texture value equal to (U.sub.2,V.sub.2). The U and V values identify a texture map location to be sampled from a texture map. Arbitrary texture color samples may be linearly interpolated from the vertices of the object T. For illustrative purposes only, a screen space sampling point P at (X.sub.P,Y.sub.P) having texture values (U.sub.P,V.sub.P) is arbitrarily selected.
In order to generate a texture map, planar equations are first computed from the information of FIG. 1. The vertices of the triangle illustrated in FIG. 2 define a planar equation (a.sub.u x+b.sub.u y+c.sub.u =0) generated conventionally from the known "U" texture values (U.sub.0,U.sub.1 and U.sub.2). The vertices of the triangle illustrated in FIG. 3 represent a 10 different planar equation (a.sub.v x+b.sub.v y+c.sub.v =0) generated conventionally from the known "V" texture values (V.sub.0,V.sub.1 and V.sub.2). As illustrated by FIGS. 2 and 3, individual values for U and for V are determinable from the X and Y geometric coordinates for each of the vertices.
FIG. 4A represents a texture map 400 generated conventionally from the planar equations represented by FIGS. 2 and 3. For a particular geometric coordinate in screen space (X.sub.P,Y.sub.P, FIG. 1), texture values U.sub.P and V.sub.P can be computed from the planar equations represented by FIGS. 2 and 3 respectively, and, using point sampling or bi-linear sampling, a corresponding texture may be extracted from texture map 400. Using point sampling, the texture represented by texture element (texel) 410 is extracted.
Texture values are generated using bi-linear sampling by texel 420 interpolation as illustrated by FIG. 4B. Namely, a unit square 430 is computed about sampling point S. The bi-linear texture values are determined by interpolating linearly in the U and V directions from the texture values for the vertices of the unit square. As illustrated, the unit square resides within parts of texels A, B, C and D. Interpolation in the horizontal direction is based on U.sub.-- frac and interpolation in the vertical direction is based on V.sub.-- frac. Interpolation based on U.sub.-- frac is performed by adding the fractional color contribution of texel A to the fractional color of texel B, and adding the fractional color contribution of texel C to the fractional color contribution of texel D. The two interpolated U.sub.-- frac values are in turn interpolated likewise based on the fraction V.sub.-- frac. The resulting interpolated color value represents the texture color sample to be used for point P.
A reason for performing bi-linear interpolation is to avoid texture "truncation-snapping." That is, as an object moves in screen space, it is undesirable for the re-sampled texture image on that object to jump from one texture sample point to the next on a given pixel of geometry. It is preferable for the re-sampled texture image to move gradually with the geometry from one frame to the next, and this is accomplished using bi-linear sampling.
FIG. 5A illustrates how a mip-mapped texture map (mip-map) 00 is generated. A mip-map 500 includes a set of associated successive texture maps 510 which include incremental levels of detail.
A method for generating a mip-map 500 begins by first obtaining a detailed texture map 520. A less-detailed texture map 540 is generated from detailed map 520 by filtering from texel blocks of the detailed map. A common filter, called a "box" filter, averages a two-by-two block of texels. For example, a texel 550 of a less detailed map 540 may be averaged from four texels 530 of detailed map 520. An even less (the least shown) detailed map 570 may be generated by averaging from less-detailed map 540. For example, texel 560 of least-detailed map 570 may be determined by averaging the four texels of less-detailed map 540. The process of texel averaging typically continues until a map 570 having only one texel is generated. Although FIG. 5A illustrates three levels of detail maps, any number of maps greater than one may be used for mip-mapped sampling.
As an object is rendered, successive (X,Y) coordinates are selected for texture mapping. For a successive (X,Y) coordinate, the sampling point on the texture map moves a distance .DELTA.U ,.DELTA.V, which is referred to as a sampling "stride." The sampling stride is smaller for a less-detailed map. In the FIG. 5A example, the sampling stride (i.e., the length of the arrow from point S to point S1) is reduced by fifty percent from detailed map 520 to less-detailed map 540 and reduced another fifty percent from less-detailed map 540 to least-detailed map 570.
Tri-linear sampling is preferably used to determine the texture color for an example sampling point P in three-dimensional space, although point or bi-linear sampling could be used. Tri-linear sampling, like bi-linear sampling, interpolates textures from surrounding texels. However, tri-linear sampling also interpolates between successive maps 510 of a mip-map 500, to avoid texture truncation snapping as images virtually move nearer or further in the distance. When rendering a three-dimensional image, the virtual distance from the object to the user is determined and used for selecting the level of detail, and thus the texture map, appropriate for rendering the object. For example, detailed map 520 may be used when the virtual distance is closer than 50 meters and less detailed map 540 may be used when the virtual distance is further than 100 meters. FIG. 5B illustrates the bi-linear interpolation equation for detailed map 520 sampling point S, based on u.sub.-- frac.sub.-- high and v.sub.-- frac.sub.-- high. FIG. 5C illustrates the bi-linear interpolation equation for the next lower detailed map 540 sampling point S, based on u.sub.-- frac.sub.-- low and v.sub.-- frac.sub.-- low. If the virtual distance is about 75 meters, then a tri-linear texture value for a sampling point S.sub.I halfway between the bi-linear values computed in FIGS. 5B and 5C will preferably be selected. FIG. 5D illustrates the tri-linear sampling point S.sub.I, which is generated by linearly interpolating a fraction fs.sub.-- frac based on the virtual distances of the user's perspective to the image. It will be appreciated that for point or bilinear sampling, the more detailed of the two most appropriate maps is preferably used to obtain a more accurate value.